/**
 * 节点类
 */
class Tree {
  constructor (val) {
    this.val = val
    this.left = null
    this.right = null
  }
}
/**
 * 创建二叉树
 * @param {*} list 
 * @returns 
 */
function buildBinaryTree (list) {
  return helper(list, 0)
}
function helper (list, index) {
  if (index >= list.length || list[index] === null || list[index] === undefined) {
    return null
  }
  const root = new Tree(list[index])
  root.left = helper(list, 2 * index + 1)
  root.right = helper(list, 2 * index + 2)
  return root
}
const nums = [2, 1, 3];
// const root = buildBinaryTree(nums);
// console.log(root);
/**
 * 有效二叉搜索树定义如下 节点左子树只包含小于当前节点的数
 * 节点的右子树只包含大于当前节点的数
 * 所有左子树和右子树必须也是二叉搜索树
 * @param {*} root 
 */
// 二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树，其中每个节点的值都大于其左子树中任意节点的值，并且小于其右子树中任意节点的值。

// function helper (node, low, high) {
//   if (node === null) return true
//   let val = node.val
//   // 不能小于下边界
//   if (low !== null && val <= low) return false
//   // 不能大于上边界
//   if (high !== null && val >= high) return false
//   // 左子树的上边界是当前节点值
//   if (!helper(node.left, low, val)) return false;
//   // 右子树的下边界是当前节点值
//   if (!helper(node.right, val, high)) return false
//   return true
// }
// var isValidBST = function (root) {
//   console.log(root);
//   return helper(root, null, null)
// }
var isValidBST = function (root) {
  if (root === null) return true
  let node = root
  let stack = []
  let pre = -Infinity
  while (stack.length > 0 || node !== null) {
    if (node) {
      stack.push(node)
      node = node.left
    } else {
      node = stack.pop()
      if (pre >= node.val) {
        return false
      }
      pre = node.val
      node = node.right
    }
  }
  return true
}
let root = {
  val: 2,
  left: { val: 1, left: null, right: null },
  right: { val: 3, left: null, right: null }
}
console.log(isValidBST(root));
